package com.lft.ten_commonly_used_algorithms04.kmp;

/**
 * KMP 算法
 */
public class KmpAlgorithm {
	public static void main(String[] args) {
		String str1 = "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDABD";
		System.out.println(kmp(str1, str2));
	}
	
	/**
	 * KMP算法方法
	 * @param str1 原字符串
	 * @param str2 子串
	 * @return 返回第一个匹配的索引。没有找到返回 -1
	 */
	public static int kmp(String str1, String str2) {
		// 获取子路的部分匹配表。
		int[] partialMatchArrays = partialMatchTable(str2);
		// 遍历
		for (int i = 0, j = 0; i < str1.length(); i++) {
			// 当两个不相等时处理，【KMP 算法核心】
			while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = partialMatchArrays[j - 1];
			}
			
			// 当两个相等时处理
			if (str1.charAt(i) == str2.charAt(j)) {
				j++;
			}
			if (j == str2.length()) {
				return i - j + 1;
			}
		}
		// 获取到
		return -1;
	}
	
	/**
	 * 获取子串的部分匹配表。
	 * @param str2 子串
	 * @return 部分匹配表
	 */
	public static int[] partialMatchTable(String str2) {
		int[] resutl = new int[str2.length()];
		// 如果字符串长度为1，部分匹配值就是0
		resutl[0] = 0;
		for (int i = 1, j = 0; i < str2.length(); i++) {
			// str2.charAt(i) != str2.charAt(j)时，需要从 result[j-1]获取新的j
			// 循环查找，直到找到相等的时候才退出循环。【KMP 算法核心】
			while (j > 0 && str2.charAt(i) != str2.charAt(j)) {
				j = resutl[j - 1];
			}
			// str2.charAt(i) == str2.charAt(j) 满足时，部分匹配值就是 +1;
			if (str2.charAt(i) == str2.charAt(j)) {
				j++;
			}
			resutl[i] = j;
		}
		return resutl;
	}
}
